1. Field of the Invention
This invention relates generally to optimizing compilers for development of computer programs for use on a computer, and more particularly to Fortran 90 WHERE construct optimization, compilation, and interpretation.
2. Description of the Related Art
Recently, the X3J3 subcommittee of the American and National Standards Institute (ANSI), in collaboration with a corresponding International Standards Organization (ISO) group ISO/IEC JTC1/SC22/WG5, approved a new standard for the Fortran programming language. This new Fortran programming language standard is generally denominated the "Fortran 90" language standard and is also in the art denominated the "Fortran 90 Array Language" standard. While maintaining compatibility with and providing support for the previous "FORTRAN 77" language standard, this new Fortran 90 Array language standard defines many new programming constructs and functions.
Among these new features are the "array language" protocols. Fortran programs in the Fortran 90 language may specify operations to be performed on entire arrays or on specific sections of arrays. To facilitate these new array operations, the Fortran 90 standard defines a new class of array functions denominated "WHERE" constructs. The Fortran 90 standard is promulgated by the ISO as the International Fortran Standard specification number ISO/IEC 1539:1991 and is promulgated by the ANSI as specification number ANSI X3.198-199x.
The new features promulgated in the Fortran 90 language standard create new challenges for existing Fortran compiler and preprocessor technology. The existing FORTRAN 77 compilers do not address the array constructor functions and must be completely rewritten and restructured to accommodate the Fortran 90 standard. The new problems created by Fortran 90 array constructors can be appreciated with reference to the FORTRAN compiler art.
FIG. 1 illustrates a procedure for translating a FORTRAN program 10 to create an executable binary object program 12. A lexical/syntax analysis 14 is conducted to transform source program 10 to a first intermediate language program 16. First intermediate language program 16 is then processed by an optimization routine 18 to create a second intermediate language program 20, which is then directly interpreted by the code generation routine 22 to create object program 12.
Lexical/syntax analysis routine 14 and code generation routine 22 are easily defined in terms of the Fortran 90 specification and the machine binary code set, respectively. Thus, it is optimization routine 18 that is primarily affected by the new Fortran 90 standard. Optimization routine 18 is illustrated in FIG. 2 as it is understood in the art. Optimization processing is achieved by first performing a control flow analysis in routine 24 of first intermediate language 16. Control flow analysis routine 24 provides the control flow data 26, which are then passed to a data-flow analysis routine 28 wherein first intermediate language program 16 is analyzed for data flow. Data-flow analysis routine 28 produces the data-flow data 30. Finally, a program transformation procedure 32 accepts control flow data 26, data-flow data 30, and first intermediate language program 16 to produce second intermediate language program 20.
Despite extensive effort in the compiler art related to optimization, the array transformation functions introduced by the new Fortran 90 standard bring with them new inefficiencies in storage and processing, and there is an accordingly clearly-felt need in the art for more efficient compiling procedures suitable for application to these new intrinsic Fortran 90 array transformation functions.
This problem can be better understood by considering an example. The Fortran 90 standard specification defines a WHERE statement as having the following form:
WHERE (mask-expr) var=expr PA1 WHERE (mask-expr) PA1 [ELSEWHERE] PA1 END WHERE PA1 WHERE (A&gt;0.0) PA1 END WHERE PA1 Evaluate the mask expression, mask-expr, and keep the result; PA1 Evaluate each assignment statement, "var=expr", inside the WHERE block as if it is the WHERE statement "WHERE (mask-expr) var=expr"; and PA1 Evaluate each assignment statement, "var=expr", inside the ELSEWHERE block as if it is the statement "WHERE (.not. mask-expr) var=expr". PA1 Treat the WHERE construct as a sequence of WHERE statements; PA1 Then scalarize each WHERE statement as before; PA1 Compute intrastatement data dependence for each WHERE statement and find the correct scalarization for each WHERE statement; and PA1 Compute interstatement data dependence between every pairs of statements and iteratively try to fuse these statements into the same loop.
in which the expression, "expr", of the assignment statement, "var=expr", is evaluated for all elements where the mask expression, "mask-expr", is true, and the result is assigned to the corresponding elements of "var".
The Fortran 90 standard specification also defines a WHERE construct as having the following syntax:
[assignment statement] PA2 [assignment statement] PA2 A=LOG(A) LOG is invoked only for positive elements. PA2 A=A/SUM(LOG(A)) LOG is invoked for all elements.
in which the masked array assignment statement is used to mask the evaluation of expressions and the assignment of values on an element-by-element basis, according to the value of a logical expression. The WHERE statement and WHERE construct are analogous to the IF statement and the IF construct in the Fortran 77 language.
The execution semantics of a WHERE construct is defined as follows. First, the mask expression is evaluated and stored. Each assignment statement in the WHERE construct is then evaluated, in sequence, as if it is the statement "WHERE (mask-expr) var=expr". Then each assignment statement in the ELSEWHERE block is evaluated, in sequence, as if it is the statement "WHERE (.not. mask-expr) var=expr". Note that the Fortran 90 language definition forbids nesting of WHERE constructs, and only array assignment statements are allowed within a WHERE construct.
The mask expression in a WHERE statement or construct controls the elements on which elemental operations such as "+" and "*" are performed, but does not control the elements on which transformational intrinsic functions (TIFs), such as SUM, are performed. This distinction is revealed in the following example from the Fortran 90 language standard document:
To invoke LOG only for positive elements in the TIF SUM function, a mask should be passed explicitly to the TIF SUM function by writing SUM(LOG(A), MASK=A&gt;0.0).
The conventional way of optimizing WHERE Constructs is taught by John R. Allen ("Dependence Analysis for Subscripted Variables and its Application to Program Transformation, PhD thesis, Rice University, 1983). Allen teaches a conventional method of scalarizing WHERE Constructs as a simple extension to scalarizing array assignment statements.
As an example of Allen's teachings, consider the following WHERE statement:
WHERE (A(0:n-1).eq. 0) A(1:n)=A(2:n+1)+1. Using the legality test, those skilled in the art recognize that the assignment statement, A(1:n)=A(2:n+1)+1 with direction vector (&gt;) may be legally scalarized as the code of the following Table A:
TABLE A ______________________________________ DOi = 1, n A(i) = A(i + 1) + 1 END DO ______________________________________
However, the following code of Table B is an invalid scalarization of the WHERE statement because of the loop-carried flow dependence from A(i) in the left hand side of the expression (LHS) to A(i-1) in the mask expression:
TABLE B ______________________________________ DOi = 1, n IF (A(i - 1) .eq. 0) THEN A(i) = A(i + 1) + 1 END IF END DO ______________________________________
To obtain a valid scalarization for a WHERE statement, the dependences between the expression LHS and the mask expression need to be considered in addition to the dependences between the expression LHS and the right hand side of the expression (RHS).
This is like an IF-conversion as taught by Allen where a control dependence is treated like a data dependence. The IF-conversion approach is well suited to WHERE statements and constructs because the control dependences are simple and well structured (there are no GOTO statements) into or out of a WHERE construct, and WHERE constructs cannot be nested.
To obtain a scalarization for the example, an array temporary, mtemp(i), for the mask expression, (A(0:n-1).eq. 0), may be introduced to eliminate the flow dependence as shown in the following Table C:
TABLE C ______________________________________ DOi = 1, n mtemp(i) = A(I-1) .eq. 0 END DO DOi = 1, n IF (mtemp(i)) THEN A(i) = A(i + 1) + 1 END IF END DO ______________________________________
All the techniques discussed earlier for array assignment statements can be applied to WHERE statements, by taking both LHS--RHS and LHS--MASK dependences into account.
The extension for introducing array temporaries is more complicated as mask and data temporaries have slightly different properties. For instance, if the i loop in the example is reversed, then the LHS--MASK direction vector will be (&gt;), and the LHS--RHS direction will be (&lt;). It appears that only a data temporary need be introduced, and not a mask temporary. However, introducing the data temporary splits the LHS=RHS statement into two statements, each of which must be guarded by the same mask expression. Therefore, forcing the introduction of a mask temporary as well. In general, the number of dimensions in the mask temporary must be greater than or equal to the number of dimensions in the data temporary.
WHERE constructs are more complicated than WHERE statements. In general, the mask expression needs to be stored in a full-sized temporary because the mask value may be needed in more than one loop nest. After the individual WHERE statements have been scalarized and optimized, fusing of their loops may be attempted. After any such loop fusion, IF-fusion on the mask expression may also be attempted if the two loop nests originated from the same WHERE block or ELSEWHERE block as the mask expression will be the same in both loop nests. Loop fusion and IF-fusion may then lead to a reduction in the size of the mask temporary.
A straight forward conventional approach to compiling a WHERE construct is to treat it as a sequence of WHERE statements. This conventional approach teaches the following steps:
An improved conventional approach for high-level optimization is to fuse this sequence of WHERE statements into the same loop, if possible. This improved approach to compile a WHERE construct is:
The conventional approaches above to compiling WHERE constructs either provide no optimization, such as the straight forward approach, or provide high-level optimization after considerable compilation time.
Thus, existing methods provide no medium-level of optimization with a fast compilation time. As such, there is a need for a method of, system for, and computer program product for, providing a medium-level of optimization for WHERE constructs with a fast compilation time.